package interview.dynamic;

import java.util.Arrays;

/**
 * dp[i] 为凑够i的数字，最少需要的硬币数
 * 那么。dp[i] = Math.min(dp[i], dp[i-coin] + 1)
 * Created by yzy on 2021-03-05 18:12
 */
public class CoinChange {

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0;

        for(int i=1; i<amount; i++){
            for(int j=0; j<coins.length; j++){
                // 只有当硬币面值小于amount数，才有计算的价值
                if(coins[j] <= i){
                    dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }












    public int coinChange_test(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);  // 都默认填充一个大于amount的无效的数
        dp[0] = 0;
        for(int i=1; i<=amount; i++){
            for(int coin : coins){
                if(i >= coin){
                    dp[i] = Math.min(dp[i], dp[i-coin] +1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }






    /**
     * 给了一堆硬币coins 和目标数字 amount
     * 要求，找到凑足amount需要的最少硬币数
     * dp[i] = 1 + dp[i-coin]
     *
     * 所以，要求的结果就是  dp[amount]
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange_test2(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        for(int i=1; i<=amount; i++){
            for(int coin : coins){
                if(i >= coin){
                    dp[i] = Math.min(dp[i], 1+dp[i-coin]);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }







}
